package SwordFingerOffer;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Q40_MinK {


    //最小的 K 个数字 ==> 大根堆 ==> 比堆顶小的进
    //O(n)
    public int[] getLeastNumbers(int[] arr, int k) {

        if (k <= 0 || arr == null || arr.length == 0){
            return new int[]{};
        }
        //默认是小根堆 ==> 需要自己改造成大根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });

        heap.add(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            //堆没满
            if (heap.size() < k){
                heap.add(arr[i]);
            }else {
                //size >= k 堆满了，比较后再说能不能进
                if (heap.peek() > arr[i]){
                    heap.poll();
                    heap.add(arr[i]);
                }
            }
        }
        int[] ans = new int[k];
        int times = heap.size();
        for (int i = 0; i < times; i++) {
            ans[i] = heap.poll();
        }
        return ans;
    }

    public static void main(String[] args) {
        Q40_MinK fun = new Q40_MinK();
        int[] arr = new int[]{3,2,1};
        System.out.println(Arrays.toString(fun.getLeastNumbers(arr, 2)));
    }
}
